package service;

import gold.utils.InputUtil;

import java.util.ArrayList;
import java.util.List;

/**
 * Created by fanzhenyu02 on 2020/8/10.
 */
class LongPathService {
    //DFS+memo serach

//    class Point{
//        public int x;
//        public int y;
//
//        public Point(int x, int y){
//            this.x = x;
//            this.y = y;
//        }
//
//        @Override
//        equals(Object o){
//            Point p = (Point)o;
//
//            return p.x == this.x && p.y == this.y;
//        }
//    }
//
//    //memo define here
//    public Map<Point, Integer> memo = new HashMap<>();

    public List<Integer> globalMaxPath = new ArrayList<>();
    public int maxLength = Integer.MIN_VALUE;

    public int findMaxIncreaingPath(int[][] matrix) {
        //special case ideification.
        if (null == matrix || matrix.length <= 0 || matrix[0].length <= 0) {
            return 0;// 0 increasing length.
        }

        int row = matrix.length;
        int col = matrix[0].length;

        for (int i = 0; i < row; ++i) {
            for (int j = 0; j < col; ++j) {
                int curLen = findMaxIncreaingPathStartFromSinglePoint(matrix, row, col, i, j);
                if (curLen > maxLength) {
                    maxLength = curLen;
                }
            }
        }

        //finally maxLenght is the result.
        for (Integer node : globalMaxPath) {
            System.out.println(node);
        }

        return maxLength;
    }

    /**
     * get longest incrasing path start from i,j
     **/
    public int findMaxIncreaingPathStartFromSinglePoint(int[][] matrix, int row, int col, int i, int j) {
        boolean[][] visited = new boolean[row][col];
        int maxLen[] = new int[1]; //using array to pass memory index instead of value passing.

        List<Integer> curSelectPath = new ArrayList<>();
        findMaxIncreaingPathStartFromSinglePointDFS(matrix, visited, row, col, i, j, curSelectPath, maxLen);
        return maxLen[0];
    }

    // DFS main body.
    public void findMaxIncreaingPathStartFromSinglePointDFS(int[][] matrix, boolean[][] visited, int row, int col, int i, int j, List<Integer> curSelectPath, int[] maxLen) {
        if (isIllegal(visited, row, col, i, j)) return;

        int cur = matrix[i][j]; //current weight.
        if (curSelectPath.isEmpty() || curSelectPath.get(curSelectPath.size() - 1) < cur) {
            // current path is match incrasing condition.
            curSelectPath.add(cur);
            visited[i][j] = true;
            maxLen[0] = Math.max(maxLen[0], curSelectPath.size());
            if (maxLen[0] > maxLength) {
                globalMaxPath = new ArrayList<>();
                for (Integer node : curSelectPath) {
                    System.out.print(node + "->");
                    globalMaxPath.add(node);
                }
            }

            // four direction serach
            findMaxIncreaingPathStartFromSinglePointDFS(matrix, visited, row, col, i - 1, j, curSelectPath, maxLen);
            findMaxIncreaingPathStartFromSinglePointDFS(matrix, visited, row, col, i + 1, j, curSelectPath, maxLen);
            findMaxIncreaingPathStartFromSinglePointDFS(matrix, visited, row, col, i, j - 1, curSelectPath, maxLen);
            findMaxIncreaingPathStartFromSinglePointDFS(matrix, visited, row, col, i, j + 1, curSelectPath, maxLen);

            // delete cur selection
            curSelectPath.remove(curSelectPath.size() - 1);
            visited[i][j] = false;
        }
    }

    public boolean isIllegal(boolean[][] visited, int row, int col, int i, int j) {
        return i < 0 || i >= row || j < 0 || j >= col || visited[i][j] == true;
    }


    public static void main(String[] args) {
        int[][] matrix = InputUtil.toDoubleIntegerArray("[\n" +
                "    [8, 3, 2],\n" +
                "    [4, 1, 5],\n" +
                "    [3, 2, 4]\n" +
                "]");

        LongPathService ls = new LongPathService();
        System.out.println(ls.findMaxIncreaingPath(matrix));

    }


}






